﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution763
{
    public IList<int> PartitionLabels2(string s)//这个方法正确，但是时间复杂度有点高，n2

    {
        IList<int> res = new List<int>();
        
      
        
        int start = 0;
        int end = 0;

        
        while (start < s.Length)
        {
            IList<char> path = new List<char>();
            path.Add(s[start]);
            for (int i = start; i < s.Length; i++)
            {

                if (path.Contains(s[i]))
                {


                    end = i;
                    //把之间的都加入
                    Addpath(s, start, end, path);
                    start = end + 1;
                }


            }
            for (int i = 1; i < path.Count; i++)
            {

                Console.Write(path[i]);
            }
            Console.WriteLine(path.Count);
            res.Add(path.Count-1);
        }
      
        
       
        return res;
    }

    private void Addpath(string s, int start, int end, IList<char> path)
    {
        for(int i = start; i <= end; i++)
        {
            path.Add(s[i]);
        }
    }

    public IList<int> PartitionLabels(string s)//遍历一次

    {
        IList<int> res = new List<int>();
        Dictionary<char,int> map= new Dictionary<char,int>();//char是英文字母，int是最远的距离
        //可以使用数组优化


       



        for (int i = 0; i < s.Length; i++)
        {
            map[s[i]] = i;


        }
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.Length; i++)
        {
            end= Math.Max(end, map[s[i]]);//这组字母的最远范围
            if (i == end)
            {
                res.Add(end-start+1);
                start = end + 1;
                end = 0;
            }


        }

        return res;
    }
}
class Program763
{


    static void Main763(string[] args)
    {
        //string s = "ababcbacadefegdehijhklij";
        string s = "caedbdedda";

        Solution763 solution = new Solution763();
        IList<int> res=solution.PartitionLabels(s);
        for (int i = 0; i < res.Count; i++) {
            Console.WriteLine(res[i]);
        }
        

    }
}